package com.code.array;

public class listNode {


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }



    /**
     * 160。相交链表  具体思路可参考灵神
     *
     初始化两个指针 p=headA, q=headB。
     不断循环，直到 p=q。
     每次循环，p 和 q 各向后走一步。具体来说，如果 p 不是空节点，那么更新 p 为 p.next，否则更新 p 为 headB；如果 q 不是空节点，那么更新 q 为 q.next，否则更新 q 为 headA。
     循环结束时，如果两条链表相交，那么此时 p 和 q 都在相交的起始节点处，返回 p；如果两条链表不相交，那么 p 和 q 都走到空节点，所以也可以返回 p，即空节点。
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p=headA;
        ListNode q=headB;
        while(p!=q){

            if(p==null){
                p=headB;
            }else{
                p=p.next;
            }

            if(q==null){
                q=headA;
            }else{
                q=q.next;
            }

        }
        return p;
    }

    /**
     * 206.反转链表
     *  https://www.bilibili.com/video/BV1sd4y1x7KN/?vd_source=f8e7ecfd2de9e15f5cd47a12393fc38b
     *
     *   思想  //反转链采用头插法实现
     *     //例如： 1->2->3->null   反转过来就是  null <- 1 <- 2 <- 3   ========= 3->2->1>null
     *     //需要初始化 两个指针    当前指针，前指针； 在头插法时 还要初始化一个next指针
     * @param head
     * @return
     */

    public ListNode reverseList(ListNode head) {
        ListNode cur=head;  //当前指针
        ListNode pre=null;   //前指针
        while(cur!=null){
            ListNode nextNode=cur.next;
            cur.next=pre;     //重点理解 ！！！！
            pre=cur;
            cur=nextNode;
        }
        return pre;
    }

    /**
     * 141.环形链表
     *      快慢指针
     *  思想：   //兔子乌龟 做法
     *         //写一个慢指针和一个快指针；如果是环形链表，那么他俩肯定会相遇，
     *         //                      如果访问到null的链表节点那么明不是环形链表
     *
     *    重点：
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        //下面是重点，没有判断slow是否为null，是因为fast在slow前面如果fast为null了；那么slow也可能为空
        // while里面写 fast.next!=null  是因为 循环内 fast=fast.next.next； 如果不写fast.next!=null，那么在非环形链表可能会报越界
        while(fast!=null && fast.next!=null){
            slow=slow.next; //乌龟走一步
            fast=fast.next.next; //兔子走两步
            if(slow==fast){ //说明有环
                return true;
            }
        }
        return false;
    }

    /**
     * 142.环形链表2
     *
     * 图解地址： https://leetcode.cn/problems/linked-list-cycle-ii/solutions/1999271/mei-xiang-ming-bai-yi-ge-shi-pin-jiang-t-nvsq/?envType=study-plan-v2&envId=top-100-liked
     *  使用141的快慢指针， 设 从头节点到入环节点为a，环路长c； 假设慢指针走了b步，那么快指针走了2b步
     *                    即  有快指针等式  2b=b+kc  成立   ===>  b=kc  ===>  b-a=kc-a
     *                    由上述推到得出  当快慢指针在相遇点相遇时， 此时满指针再走a步即到达入环点
     *                     假如  在相遇点头指针和满指针一起移动a步，那么 他俩会同时在入环点相遇
     *
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                while(slow!=head){  //再走a步   在相遇点，头节点和 慢指针一共走a步，一定会到达入环点
                    slow=slow.next;
                    head=head.next;
                }
                return slow;
            }
        }
        return null;
    }

    /**
     * 21.合并两个有序链表
     *
     * 这个题不能直接使用result.next进行接收， 如果直接使用result。next接受的话，最后返回的时候  返回result，只会返回最后一个节点
     *
     * 使用哨兵节点，并给他赋予一个指针； 使用指针进行next添加操作
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode result=new ListNode(-1);
        ListNode cur=result;
        while (list1!=null && list2!=null){
            if(list1.val<list2.val){
                cur.next=list1;
                list1=list1.next;
            }else{
                cur.next=list2;
                list2=list2.next;
            }
            cur=cur.next;
        }
        if(list1!=null){
            cur.next=list1;
        }else if(list2 !=null){
            cur.next=list2;
        }
        return result.next;  //因为节点里面有一个哨兵节点，所以返回的是next
    }

    /**
     *2. 两数相加
     *
     * deepseek给出的答案
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result=new ListNode(0);
        ListNode cur=result;
        int carry = 0; // 进位值

        //判断条件 考虑
        // l1、l2 不等长，短的直接补0，并且考虑 进位
        while(l1!=null || l2!=null || carry!=0){
            int a= (l1!=null) ? l1.val:0;
            int b= (l2!=null) ? l2.val :0;

            int sum=a+b+carry;   //要将进位加入进去，首次循环默认进位是0
            carry=sum/10;    //int 类型是整形，小数点直接截取所以 使用除法获取是否有进位值
            cur.next=new ListNode(sum%10);  //初始化新链表
            cur=cur.next;

            // 移动链表指针（如果存在）
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return result.next;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     *
     * 暴力破解  秒了    先遍历一共有多少个元素，然后 总数-n+1，就是正向要删除的值
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEndBaoLi(ListNode head, int n) {
        ListNode cur=head.next;
        ListNode pre=head;
        ListNode test=head;
        int temp=1;
        int total=0;
        while(test!=null){
            total++;
            test=test.next;
        }

        n=total-n+1;

        if(temp==n){
            return head.next;
        }

        while(cur!=null){
            temp++;
            if(temp==n){
                pre.next=cur.next;
                return head;
            }
            pre=pre.next;
            cur=cur.next;
        }
        return head;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     *
     *https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solutions/2004057/ru-he-shan-chu-jie-dian-liu-fen-zhong-ga-xpfs/?envType=study-plan-v2&envId=top-100-liked
     *
     * 想象一把长度为n的尺子，当尺子平移到链表的最后一个节点时，这时尺子的左端点正好指向要删除的倒数第n个节点
     * 删除节点 是将待删除的节点  前面的一个节点，next=next.next;  所以将尺子平移到 链表的倒数第二个节点 这时尺子左端点指向 待删除的pre节点
     *
     * while 循环中 条件为 cur.next!=null  指向倒数第二个节点    cur!=null 指向倒数第一个节点
     *
     * 增加哨兵节点， 可简化删除头节点问题
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy=new ListNode(0,head); //增加哨兵节点  可简化删除头节点问题
        //构造一把长度为n的尺子
        ListNode left=dummy;
        ListNode right=dummy;
        while(n-->0){
            right=right.next;
        }
        //让尺子的右端指向链表末尾，这时尺子的左端点就正好在要删除的倒数n节点上
        //所以这里 是将right停到倒数第二个节点上，这样left节点正好指向 待删除节点的前一个节点
        while(right.next!=null){
            left=left.next;
            right=right.next;
        }
        //删除节点 是将待删除的节点  前面的一个节点，next=next.next;
        left.next=left.next.next;
        return dummy.next;
    }


    /**
     * 24.两两交换链表中的节点
     *
     * https://leetcode.cn/problems/swap-nodes-in-pairs/solutions/2374872/tu-jie-die-dai-di-gui-yi-zhang-tu-miao-d-51ap/?envType=study-plan-v2&envId=top-100-liked
     *
     * 大概思路就是 先确定循环条件，因为要有两个节点才有交换的意义，所以 循环条件是  node1!=null &&node1.next!=null
     *
     *                              0     ->    1->    2 ->    3    ->4
     *                第一次循环    node0      node1   node2   node3
     *                第二次循环                       node0   node1
     *
     *
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        ListNode dummy=new ListNode(0,head);
        ListNode node0=dummy;
        ListNode node1=head;
        while(node1!=null && node1.next!=null){   //要有两个节点不为null 才能交换
            ListNode node2=node1.next;
            ListNode node3=node2.next; //中间节点，防止链表丢失

            node0.next=node2;
            node2.next=node1;
            node1.next=node3;

            node0=node1;
            node1=node3;
        }
        return dummy.next;
    }

    /**
     *
     *25.K个一组反转链表
     *
     *  使用到了反转链表得方法  (自己写+deepseek)
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy=new ListNode(0,head);
        ListNode cur=dummy;
        ListNode left=head;
        ListNode right=head;
        int temp=0;
        while(right!=null){
            temp++;
            if(temp==k){
                ListNode nodeR=right.next;
                right.next=null;  //方便下面 调用反转方法 时判空条件

                //调用反转链表
                ListNode reverseNode=reverseList(left);
                cur.next=reverseNode;
                left.next=nodeR;
                //重新设置节点进行下一轮得反转
                cur=left;
                left=left.next;
                right=left;   //这里写left  不要写left.next了，因为left已经向后移动一个了
                temp=0;
                // 重点  如果下一组为空，提前结束   这里面因为left已经到了最右端点，并且有一个left.next 所以要判断是否为null
                if(left==null) break;
            }else{
                right=right.next;
            }
        }
        return dummy.next;
    }

    public static void main(String[] args) {

    }
}
